/// @tags:
#include <cstdio>
#include <iostream>
#define rint register int

using std::cin;
using std::cout;

namespace BlueQuantum {

typedef long long LL;

constexpr int maxn = 1e6 + 3, mod = 1e9 + 7;

int np[maxn];
int pri[maxn], pcnt;

struct Matrix {
  int a[2][2];

  inline Matrix(int x = 0) {
    for (int i = 0; i < 2; ++i)
      for (int j = 0; j < 2; ++j) a[i][j] = i == j ? x : 0;
  }

  inline int *operator[](int index) { return a[index]; }

  inline Matrix operator*(const Matrix &rhs) const {
    Matrix res;
    for (int i = 0; i < 2; ++i)
      for (int j = 0; j < 2; ++j)
        for (int k = 0; k < 2; ++k) res.a[i][j] = (res[i][j] + (LL)a[i][k] * rhs.a[k][j]) % mod;
    return res;
  }

  inline Matrix operator^(int exp) const {
    Matrix res(1), base(*this);
    for (; exp; exp >>= 1, base = base * base)
      if (exp & 1) res = res * base;
    return res;
  }
};

inline LL qpow(LL base, int exp = mod - 2) {
  LL res(1);
  for (; exp; exp >>= 1, base = base * base % mod)
    if (exp & 1) res = res * base % mod;
  return res;
}

inline int getPhi(int n) {
  int res = n;
  for (int j = 1; pri[j] * pri[j] <= n; ++j)
    if (n % pri[j] == 0) {
      int d = pri[j];
      res = res / d * (d - 1);
      while (n % pri[j] == 0) n /= pri[j];
    }
  if (n != 1) res = res / n * (n - 1);
  return res;
}

inline LL getF(int n, int k) {
  if (n == 1)
    return 1;
  else if (n == 2)
    return (1 + k * 2) % mod;
  else {
    Matrix trans;
    trans[0][0] = 1, trans[0][1] = 1;
    trans[1][0] = k, trans[1][1] = 0;
    Matrix a = trans ^ (n - 3);
    Matrix b = a * trans;
    int f1 = (a[0][0] + (LL)a[0][1] * k % mod) % mod;
    int f2 = (b[0][0] + (LL)b[0][1] * k % mod) % mod;
    int f3 = (b[1][0] + (LL)b[1][1] * k % mod) % mod;
    return (f2 + f3 + (LL)k * f1) % mod;
  }
}

int calc(int d, int k, int n) { return getF(d, k) * getPhi(n / d) % mod; }

inline int main() {
  for (int i = 2; i < maxn; ++i) {
    if (np[i] == false) pri[++pcnt] = i;
    for (int j = 1; j <= pcnt && pri[j] * i < maxn; ++j) {
      np[pri[j] * i] = true;
      if (i % pri[j] == 0) break;
    }
  }
  int n, k;
  cin >> n >> k;
  LL ans = 0;
  for (int i = 1; i * i <= n; ++i)
    if (n % i == 0) {
      (ans += calc(i, k, n)) %= mod;
      if (i * i != n) (ans += calc(n / i, k, n)) %= mod;
    }
  cout << ans * qpow(n) % mod;
  return 0;
}

}  // namespace BlueQuantum

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("bracelet.in", "r", stdin);
  freopen("bracelet.out", "w", stdout);
#endif
#endif

  std::ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  return BlueQuantum::main();
}
